package com.algorithm.binarysearch;

import java.util.Arrays;

/**
 * 二分查找
 */
public class BinarySearch {


    /**
     * 二分查找基础版
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 找到返回目标值的索引
     * 否则返回 -1
     */
    public static int binarySearch(int[] arr, int target) {
        int i = 0, j = arr.length - 1;

        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target == arr[m]) {
                return m;
            } else if (target < arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找改动版
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 找到返回目标值的索引
     * 否则返回 -1
     */
    public static int binarySearch2(int[] arr, int target) {
        int i = 0, j = arr.length;

        while (i < j) {
            int m = (i + j) >>> 1;
            if (target == arr[m]) {
                return m;
            } else if (target < arr[m]) {
                j = m;
            } else {
                i = m + 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找平衡版
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 找到返回目标值的索引
     * 否则返回 -1
     */
    public static int binarySearch3(int[] arr, int target) {
        int i = 0, j = arr.length;

        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (target == arr[i]) {
            return i;
        }
        return -1;
    }

    /**
     * 二分查找Leftmost
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 找到返回目标值最靠左的索引
     * 否则返回 -1
     */
    public static int binarySearchLeftmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找Leftmost2
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 查找目标值前任
     * 否则返回 -1
     */
    public static int binarySearchLeftmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return j;
    }

    /**
     * 二分查找Leftmost3
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 查找重复元素最左侧目标值，没有返回插入位置
     * 否则返回 -1
     */
    public static int binarySearchLeftmost3(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 二分查找Rightmost
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 找到返回目标值最靠右的索引
     * 否则返回 -1
     */
    public static int binarySearchRightmost1(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else if (target > arr[m]) {
                i = m + 1;
            } else {
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    /**
     * 二分查找Rightmost2
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 查找目标值后任
     * 否则返回 -1
     */
    public static int binarySearchRightmost2(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i;
    }

    /**
     * 二分查找Rightmost3
     *
     * @param arr:    待查找的 升序数组
     * @param target: 查找的 目标值
     * @return: 查找重复元素最右侧目标值
     */
    public static int binarySearchRightmost3(int[] arr, int target) {
        int i = 0, j = arr.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < arr[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return j;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 12, 15, 18, 24};
        int i = binarySearch(arr, 7);
        System.out.println("找到的目标索引i为:" + i);
        int j = binarySearch2(arr, 8);
        System.out.println("找到的目标索引j为:" + j);
        int k = binarySearch3(arr, 18);
        System.out.println("找到的目标索引k为:" + k);

        int target = 19;
        int m = Arrays.binarySearch(arr, target);
        System.out.println("找到的目标索引m为:" + m + "  插入点为:" + (-m - 1));

        //插入数字19到数组arr
        if (m < 0) {
            int insertIndex = Math.abs(m + 1);
            int[] b = new int[arr.length + 1];
            System.arraycopy(arr, 0, b, 0, insertIndex);
            b[insertIndex] = target;
            System.arraycopy(arr, insertIndex, b, insertIndex + 1, arr.length - insertIndex);
            System.out.println(Arrays.toString(b));
        }

        System.out.println("--------------------------------------------");

        int[] arr2 = {1, 2, 4, 4, 4, 8, 10,10, 10, 15, 19, 22};
        //找最左侧目标索引
        int left = binarySearchLeftmost1(arr2, 10); //6 else -1
        System.out.println("找到的目标索引i为:" + left);
        //找最右侧目标索引
        int right = binarySearchRightmost1(arr2, 10); //8 else -1
        System.out.println("找到的目标索引i为:" + right);

        //查找目标值前任
        int left2 = binarySearchLeftmost2(arr2, 10); //5
        System.out.println("查找目标值前任:" + left2);
        //查找目标值后任
        int right2 = binarySearchRightmost2(arr2, 10); //9
        System.out.println("查找目标值后任:" + right2);

        //查找目标值或插入位置
        int left3 = binarySearchLeftmost3(arr2, 10); //6
        System.out.println("查找目标值或插入位置:" + left3);
        //查找目标值或插入位置
        int right3 = binarySearchRightmost3(arr2, 10);//8
        System.out.println("查找重复元素最右侧目标值的索引:" + right3);
    }
}
